/*
 * @lc app=leetcode.cn id=139 lang=cpp
 *
 * [139] 单词拆分
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
// 1.动态规划
        int n = s.length();
        vector<int> dp(n+1,0);
        dp[0] = 1;
        for(int i = 0;i < n;i++) {
            for(int j = i+1;j <= n;j++) {
                string subs = s.substr(i, j - i);
                if (find(wordDict.begin(), wordDict.end(), subs) != wordDict.end() && dp[i])
                    dp[j] = 1;
            }
        }
        return dp[n];
    }
};
// @lc code=end

